# LeetCode 765. 情侣牵手
# https://leetcode.cn/problems/couples-holding-hands/description/
import copy
import random
from typing import List


class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        result = 0
        n = len(row)
        parents = [i for i in range(n)]
        sizes = {i: 1 for i in range(n)}

        def find(x):
            if parents[x] != x:
                parents[x] = find(parents[x])
            return parents[x]

        def union(x, y):
            x = find(x)
            y = find(y)
            if x == y:
                return
            if sizes[x] < sizes[y]:
                x, y = y, x
            parents[y] = x
            sizes[x] += sizes[y]

        for i in range(0, n, 2):
            union(row[i], row[i + 1])

        for i in range(0, n, 2):
            parent = parents[i]
            if parent == parents[i + 1]:
                continue
            parents_c = copy.deepcopy(parents)
            parents_c.pop(i)
            find_index = parents_c.index(parent) + 1
            parents[i + 1], parents[find_index] = parents[find_index], parents[i + 1]
            result += 1
        return result


def duipai(row):
    result = 0
    row = [x//2 for x in row]
    for i in range(0, len(row), 2):
        couple_id = row[i]
        if couple_id == row[i + 1]:
            continue
        row_c = copy.deepcopy(row)
        row_c.pop(i)
        find_index = row_c.index(couple_id) + 1
        row[i + 1], row[find_index] = row[find_index], row[i + 1]
        result += 1
    return result


if __name__ == '__main__':
    # row = [0,2,1,3]
    # row = [0, 2, 3, 4, 5, 1]
    # print(Solution().minSwapsCouples(row))

    for i in range(1000):
        row = random.sample(range(0, 10), 10)
        result0 = Solution().minSwapsCouples(row)
        result1 = duipai(row)
        if result0 != result1:
            print(row, result0, result1)
            assert 0
